// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include <windows.h>
//
// // 图的邻接矩阵存储结构
// #define MaxVertexNum 100 // 最大顶点数
//
// typedef char VertexType; // 顶点数据类型
// typedef int EdgeType;    // 权值数据类型
//
// typedef struct {
//     VertexType Ver[MaxVertexNum];          // 顶点表
//     EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
//     int vexnum, arcnum;                    // 顶点数和边数
// } MGraph;
//
// // 图的邻接表存储结构
//
// // 边表节点（用于存储图的边信息）
// typedef struct ArcNode {
//     int adjvex;          // 该边指向的顶点索引
//     struct ArcNode* next; // 指向下一条边的指针
// } ArcNode;
//
// // 顶点表节点（用于存储图的顶点信息及其关联的边）
// typedef struct VNode {
//     VertexType data;    // 顶点的具体数据
//     ArcNode* first;     // 指向该顶点的第一条边
// } VNode, AdjList[MaxVertexNum];
//
// // 图的邻接表表示
// typedef struct {
//     AdjList vertices;   // 顶点数组，每个元素代表一个顶点及其边
//     int vexnum, arcnum; // 顶点数和边数
// } ALGraph;
//
// // 访问标记数组（用于遍历时记录哪些顶点已访问）
// bool visited[MaxVertexNum];
//
//
// // 初始化邻接矩阵图
// void InitMGraph(MGraph* G) {
//     G->vexnum = 0;
//     G->arcnum = 0;
//     for (int i = 0; i < MaxVertexNum; i++) {
//         for (int j = 0; j < MaxVertexNum; j++) {
//             G->Edge[i][j] = 0; // 初始化邻接矩阵
//         }
//     }
// }
//
// // 添加顶点到邻接矩阵图
// void AddVertexM(MGraph* G, VertexType v) {
//     if (G->vexnum < MaxVertexNum) {
//         G->Ver[G->vexnum] = v;
//         G->vexnum++;
//     }
// }
//
// // 添加边到邻接矩阵图
// void AddEdgeM(MGraph* G, int v1, int v2) {
//     if (v1 >= 0 && v1 < G->vexnum && v2 >= 0 && v2 < G->vexnum) {
//         G->Edge[v1][v2] = 1;
//         G->Edge[v2][v1] = 1; // 无向图需要对称赋值
//         G->arcnum++;
//     }
// }
//
// // 邻接矩阵的深度优先遍历（递归）
// void DFSM(MGraph* G, int v) {
//     visited[v] = true; // 标记当前顶点为已访问
//     printf("%c ", G->Ver[v]); // 访问当前顶点
//
//     // 遍历当前顶点的所有邻接点
//     for (int i = 0; i < G->vexnum; i++) {
//         if (G->Edge[v][i] == 1 && !visited[i]) {
//             DFSM(G, i); // 递归访问未访问的邻接点
//         }
//     }
// }
//
// // 邻接矩阵的深度优先遍历入口
// void DFSTraverseM(MGraph* G) {
//     // 初始化访问标记数组
//     for (int i = 0; i < G->vexnum; i++) {
//         visited[i] = false;
//     }
//
//     // 对每个未访问的顶点调用DFS
//     for (int i = 0; i < G->vexnum; i++) {
//         if (!visited[i]) {
//             DFSM(G, i);
//         }
//     }
// }
//
// // 邻接矩阵的广度优先遍历
// void BFSTraverseM(MGraph* G) {
//     // 初始化访问标记数组
//     for (int i = 0; i < G->vexnum; i++) {
//         visited[i] = false;
//     }
//
//     // 使用队列实现BFS
//     int queue[MaxVertexNum]; // 简单队列
//     int front = 0, rear = 0; // 队头和队尾指针
//
//     for (int i = 0; i < G->vexnum; i++) {
//         if (!visited[i]) {
//             visited[i] = true; // 标记为已访问
//             printf("%c ", G->Ver[i]); // 访问当前顶点
//             queue[rear++] = i; // 入队
//
//             while (front < rear) {
//                 int v = queue[front++]; // 出队
//                 for (int j = 0; j < G->vexnum; j++) {
//                     if (G->Edge[v][j] == 1 && !visited[j]) {
//                         visited[j] = true; // 标记为已访问
//                         printf("%c ", G->Ver[j]); // 访问当前顶点
//                         queue[rear++] = j; // 入队
//                     }
//                 }
//             }
//         }
//     }
// }
//
// // 初始化邻接表图
// void InitALGraph(ALGraph* G) {
//     G->vexnum = 0;
//     G->arcnum = 0;
//     for (int i = 0; i < MaxVertexNum; i++) {
//         G->vertices[i].first = NULL;
//     }
// }
//
// // 添加顶点到邻接表图
// void AddVertexAL(ALGraph* G, VertexType v) {
//     if (G->vexnum < MaxVertexNum) {
//         G->vertices[G->vexnum].data = v;
//         G->vexnum++;
//     }
// }
//
// // 添加边到邻接表图
// void AddEdgeAL(ALGraph* G, int v1, int v2) {
//     if (v1 >= 0 && v1 < G->vexnum && v2 >= 0 && v2 < G->vexnum) {
//         ArcNode* newNode = (ArcNode*)malloc(sizeof(ArcNode));
//         newNode->adjvex = v2;
//         newNode->next = G->vertices[v1].first;
//         G->vertices[v1].first = newNode;
//
//         // 无向图需要对称赋值
//         newNode = (ArcNode*)malloc(sizeof(ArcNode));
//         newNode->adjvex = v1;
//         newNode->next = G->vertices[v2].first;
//         G->vertices[v2].first = newNode;
//
//         G->arcnum++;
//     }
// }
//
// // 邻接表的深度优先遍历（递归）
// void DFSAL(ALGraph* G, int v) {
//     visited[v] = true; // 标记当前顶点为已访问
//     printf("%c ", G->vertices[v].data); // 访问当前顶点
//
//     // 遍历当前顶点的所有邻接点
//     ArcNode* p = G->vertices[v].first;
//     while (p != NULL) {
//         if (!visited[p->adjvex]) {
//             DFSAL(G, p->adjvex); // 递归访问未访问的邻接点
//         }
//         p = p->next;
//     }
// }
//
// // 邻接表的深度优先遍历入口
// void DFSTraverseAL(ALGraph* G) {
//     // 初始化访问标记数组
//     for (int i = 0; i < G->vexnum; i++) {
//         visited[i] = false;
//     }
//
//     // 对每个未访问的顶点调用DFS
//     for (int i = 0; i < G->vexnum; i++) {
//         if (!visited[i]) {
//             DFSAL(G, i);
//         }
//     }
// }
//
// // 邻接表的广度优先遍历
// void BFSTraverseAL(ALGraph* G) {
//     // 初始化访问标记数组
//     for (int i = 0; i < G->vexnum; i++) {
//         visited[i] = false;
//     }
//
//     // 使用队列实现BFS
//     int queue[MaxVertexNum]; // 简单队列
//     int front = 0, rear = 0; // 队头和队尾指针
//
//     for (int i = 0; i < G->vexnum; i++) {
//         if (!visited[i]) {
//             visited[i] = true; // 标记为已访问
//             printf("%c ", G->vertices[i].data); // 访问当前顶点
//             queue[rear++] = i; // 入队
//
//             while (front < rear) {
//                 int v = queue[front++]; // 出队
//                 ArcNode* p = G->vertices[v].first;
//                 while (p != NULL) {
//                     if (!visited[p->adjvex]) {
//                         visited[p->adjvex] = true; // 标记为已访问
//                         printf("%c ", G->vertices[p->adjvex].data); // 访问当前顶点
//                         queue[rear++] = p->adjvex; // 入队
//                     }
//                     p = p->next;
//                 }
//             }
//         }
//     }
// }
//
// //释放动态分配的内存
// void FreeALGraph(ALGraph* G) {
//     for (int i = 0; i < G->vexnum; i++) {
//         ArcNode* p = G->vertices[i].first;
//         while (p) {
//             ArcNode* temp = p;
//             p = p->next;
//             free(temp);
//         }
//     }
// }
//
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     int choice;
//     printf("请选择图的存储结构：\n");
//     printf("1. 邻接矩阵\n");
//     printf("2. 邻接表\n");
//     scanf("%d", &choice);
//
//     if (choice == 1) {
//         MGraph G;
//         InitMGraph(&G);
//
//         // 添加顶点
//         AddVertexM(&G, 'A');
//         AddVertexM(&G, 'B');
//         AddVertexM(&G, 'C');
//         AddVertexM(&G, 'D');
//         AddVertexM(&G, 'E');
//
//         // 添加边
//         AddEdgeM(&G, 0, 1); // A-B
//         AddEdgeM(&G, 0, 2); // A-C
//         AddEdgeM(&G, 1, 3); // B-D
//         AddEdgeM(&G, 2, 4); // C-E
//
//         // 深度优先遍历
//         printf("邻接矩阵的深度优先遍历结果：\n");
//         DFSTraverseM(&G);
//         printf("\n");
//
//         // 广度优先遍历
//         printf("邻接矩阵的广度优先遍历结果：\n");
//         BFSTraverseM(&G);
//         printf("\n");
//     } else if (choice == 2) {
//         ALGraph G;
//         InitALGraph(&G);
//
//         // 添加顶点
//         AddVertexAL(&G, 'A');
//         AddVertexAL(&G, 'B');
//         AddVertexAL(&G, 'C');
//         AddVertexAL(&G, 'D');
//         AddVertexAL(&G, 'E');
//
//         // 添加边
//         AddEdgeAL(&G, 0, 1); // A-B
//         AddEdgeAL(&G, 0, 2); // A-C
//         AddEdgeAL(&G, 1, 3); // B-D
//         AddEdgeAL(&G, 2, 4); // C-E
//
//         // 深度优先遍历
//         printf("邻接表的深度优先遍历结果：\n");
//         DFSTraverseAL(&G);
//         printf("\n");
//
//         // 广度优先遍历
//         printf("邻接表的广度优先遍历结果：\n");
//         BFSTraverseAL(&G);
//         printf("\n");
//     } else {
//         printf("无效的选择！\n");
//     }
//
//     return 0;
// }